package Leetcode.动态规划;

import java.util.*;

/**
 * @ClassName 最长不含重复字符的子字符串
 * @since: 2023/7/22 17:09
 * @auth: kirito
 * @description:
 **/
public class 最长不含重复字符的子字符串 {
    public static int lengthOfLongestSubstring1(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0, len = s.length();
        for(int j = 0; j < len; j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
            dic.put(s.charAt(j), j); // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
//        Map<Character, Integer> dic = new HashMap<>();
//        int i = -1, res = 0, len = s.length();
//        for(int j = 0; j < len; j++) {
//            if(dic.containsKey(s.charAt(j)))
//                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
//            dic.put(s.charAt(j), j); // 哈希表记录
//            res = Math.max(res, j - i); // 更新结果
//        }
//        return res;
    }

    /**
     * 双指针+滑动窗口简易版本  应该是第二个循环那里导致时间复杂度有点高，
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        if(s==null || s.length()<=0){
            return 0;
        }
        if (s.trim().equals("")){
            return 1;
        }
        List<Character> list = new ArrayList<>();
        int max = 0;
        char[] chars = s.toCharArray();
        for (int j = 0; j < s.length(); j++) {
            if (!list.contains(chars[j])) {
                list.add(chars[j]);
            }else{
                list.clear();
                list.add(chars[j]);
                for(int i =j-1;j>0;i--){
                    if(chars[i]==chars[j]){
                        break;
                    }else{
                        list.add(chars[i]);
                    }
                }
            }
            max = Math.max(max,list.size());
        }
        return max;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring1(s));
    }
}
